//
// Created by LiuYou on 2021/11/30.
//

#include <iostream>
#include <vector>
#include <iterator>


namespace xiao {
    static void bubbleSortOptimization(std::vector<int>& arr) {
        if (arr.empty() || arr.size() == 1) {
            return;
        }

        // isSwap 用来标记上一次冒泡的时候是否交换过。如果没有交换过, 那就是已经有序了。就退出外部循环。
        bool isSwap = true;
        for (int i = 0; (i < arr.size() - 1) && isSwap; ++i) {
            isSwap = false;
            for (int j = arr.size() - 1; j > i; --j) {
                // 在某一趟遍历冒泡中, 如果没有可交换的, 即序列已经有序了。那么 isSwap = false, 跳出外层循环。
                // 而如果一旦进行了交换, 则 isSwap = true, 那就需要进行下一趟遍历冒泡。
                if (arr[j - 1] > arr[j]) {
                    std::swap( arr[j - 1], arr[j] );
                    isSwap = true;
                }
            }
        }
    }


/*
 * todo 笔记: 每一趟冒泡交换后, 最小的数到了最前面。
 */
    static void bubbleSort(std::vector<int>& arr) {
        if (arr.empty() || arr.size() == 1) {
            return;
        }

        // 外部循环的条件为什么是 arr.size() - 1 ?
        // todo 笔记: 因为当到 倒数第二个元素有序后, 这个序列就有序了。最后一个元素不需要排序了。这个条件和选择排序的外部循环一样的道理。
        //  当然循环的条件是 arr.size(); 也行那么就是 最后一个元素的时候: i = 4 此时内部循环中 j = 4, 内部循环的条件 j > i 不成立。
        //  所以不会执行内部循环。但是这样的话, 进行了一次 for循环 的判断, 这个判断是可以避免的。所以, 使用 arr.size() - 1; 作为
        //  外部循环的条件。
        for (int i = 0; i < arr.size() - 1; ++i) {
            for (int j = arr.size() - 1; j > i; --j) {
                if (arr[j - 1] > arr[j]) {
                    std::swap( arr[j - 1], arr[j] );
                }
            }
        }
    }

}

static void bubbleSortOptimization(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    bool isSwap = true;
    for (int i = arr.size() - 1; i > 0 && isSwap; --i) {
        isSwap = false;
        for (int j = 0; j < i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap( arr[j], arr[j + 1] );
                isSwap = true;
            }
        }
    }
}

/*
 * todo 笔记: 每一趟冒泡交换后, 最大的数到了最后面。
 */
static void bubbleSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // 为什么是 > 0, 而不是 >= 0?
    // 这个问题和之前的 arr.size() - 1 是一个道理。因为将第二个元素排好序之后, 这个序列就是有序的了。
    for (int i = arr.size() - 1; i > 0; --i) {
        for (int j = 0; j < i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap( arr[j], arr[j + 1] );
            }
        }
    }
}


int main(int argc, char** argv) {
    {
        std::vector<int> arr{3, 2, 5, 4, 1};
        bubbleSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }

    {
        std::vector<int> arr{3, 2, 5, 4, 1};
        bubbleSortOptimization( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }


    return 0;
}
